<!DOCTYPE html>












  


<html class="theme-next pisces use-motion" lang="en">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">






















<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css?v=4.7.0">

<link rel="stylesheet" href="/css/main.css?v=7.2.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=7.2.0">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=7.2.0">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=7.2.0">


  <link rel="mask-icon" href="/images/logo.svg?v=7.2.0" color="#222">







<script id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '7.2.0',
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false,"dimmer":false},
    back2top: true,
    back2top_sidebar: false,
    fancybox: false,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="Java八大排序算法">
<meta name="keywords" content="排序算法">
<meta property="og:type" content="article">
<meta property="og:title" content="Java八大排序算法">
<meta property="og:url" content="http://yoursite.com/2021/02/20/Java数据结构与算法/Java八大排序算法/index.html">
<meta property="og:site_name" content="MingRong&#39;s Boat">
<meta property="og:description" content="Java八大排序算法">
<meta property="og:locale" content="en">
<meta property="og:image" content="http://yoursite.com/2021/02/20/Java数据结构与算法/Java八大排序算法/image-20210220134535850.png">
<meta property="og:updated_time" content="2021-02-20T09:43:30.923Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Java八大排序算法">
<meta name="twitter:description" content="Java八大排序算法">
<meta name="twitter:image" content="http://yoursite.com/2021/02/20/Java数据结构与算法/Java八大排序算法/image-20210220134535850.png">





  
  
  <link rel="canonical" href="http://yoursite.com/2021/02/20/Java数据结构与算法/Java八大排序算法/">



<script id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>Java八大排序算法 | MingRong's Boat</title>
  












  <noscript>
  <style>
  .use-motion .motion-element,
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-title { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">MingRong's Boat</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
      
        <p class="site-subtitle">O Captain! My Captain!</p>
      
    
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="Toggle navigation bar">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">

    
    
      
    

    

    <a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>Home</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">

    
    
      
    

    

    <a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i> <br>Categories</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">

    
    
      
    

    

    <a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br>Tags</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">

    
    
      
    

    

    <a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>Archives</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-about">

    
    
      
    

    

    <a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i> <br>About</a>

  </li>

      
      
    </ul>
  

  

  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
            

          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2021/02/20/Java数据结构与算法/Java八大排序算法/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="MingRongChen">
      <meta itemprop="description" content="O Captain! My Captain!">
      <meta itemprop="image" content="/images/geass.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="MingRong's Boat">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">Java八大排序算法

              
            
          </h1>
        

        <div class="post-meta">

          
          
          

          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              

              
                
              

              <time title="Created: 2021-02-20 17:41:53 / Modified: 17:43:30" itemprop="dateCreated datePublished" datetime="2021-02-20T17:41:53+08:00">2021-02-20</time>
            </span>
          

          
            

            
          

          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/Java数据结构与算法/" itemprop="url" rel="index"><span itemprop="name">Java数据结构与算法</span></a></span>

                
                
              
            </span>
          

          
            
            
          

          
          

          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
                 Views:  
                <span class="busuanzi-value" id="busuanzi_value_page_pv"></span>
              </span>
            </span>
          

          <br>
          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h1 id="Java八大排序算法"><a href="#Java八大排序算法" class="headerlink" title="Java八大排序算法"></a>Java八大排序算法</h1><a id="more"></a>

<h2 id="概要"><a href="#概要" class="headerlink" title="概要"></a>概要</h2><p>八大排序算法：直接插入排序（Insertion Sort）、希尔排序（Shell Sort）、选择排序（Selection Sort）、堆排序（Heap Sort）、冒泡排序（Bubble Sort）、快速排序（Quick Sort）、归并排序（Merging Sort）、基数排序（Radix Sort），基数排序也称桶排序。</p>
<p>都属于内部排序算法，其中直接插入排序和希尔排序属于<strong>插入排序</strong>，简单选择排序和堆排序属于<strong>选择排序</strong>，冒泡排序和快速排序属于<strong>交换排序</strong>。</p>
<h2 id="直接插入排序算法"><a href="#直接插入排序算法" class="headerlink" title="直接插入排序算法"></a>直接插入排序算法</h2><p>通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。<br>如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是(n2)。</p>
<p>插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。</p>
<p>通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了要给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。</p>
<h3 id="算法描述"><a href="#算法描述" class="headerlink" title="算法描述"></a>算法描述</h3><p>一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：</p>
<p>1、从第一个元素开始，该元素可以认为已经被排序。</p>
<p>2、取出下一个元素，在已经排序的元素序列中从后向前扫描。</p>
<p>3、如果该元素（已排序）大于新元素，将该元素移到下一位置。</p>
<p>4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。</p>
<p>5、将新元素插入到该位置后。</p>
<p>6、重复步骤2~5。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 通过将较大的元素都向右移动而不总是交换两个元素</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] data)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 装载临时变量</span></span><br><span class="line">	<span class="keyword">int</span> temp;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; data.length; i++) &#123;</span><br><span class="line">		temp = data[i];</span><br><span class="line">		<span class="keyword">int</span> j = i - <span class="number">1</span>;</span><br><span class="line">		<span class="comment">// 如果前一位比当前数据要大，那么进入循环比较</span></span><br><span class="line">		<span class="keyword">for</span> (; j &gt;= <span class="number">0</span> &amp;&amp; data[j] &gt; temp; j--) &#123;</span><br><span class="line">			<span class="comment">// 往后退一个位置，让当前数据与之前前位进行比较</span></span><br><span class="line">			data[j + <span class="number">1</span>] = data[j];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 退出内层循环，则说明找到了合适的位置，并将当前数据插入合适的位置中</span></span><br><span class="line">		data[j + <span class="number">1</span>] = temp;</span><br><span class="line">	&#125;</span><br><span class="line">&#125; <span class="comment">// sort end</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 通过交换进行插入排序，借鉴冒泡排序</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sortTwo</span><span class="params">(<span class="keyword">int</span>[] data)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 装载临时变量</span></span><br><span class="line">	<span class="keyword">int</span> temp;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; data.length; i++) &#123;</span><br><span class="line">		<span class="comment">// 如果前一位比当前数据要大，那么进入循环比较，并两两交换，参考冒泡排序</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> j = i - <span class="number">1</span>; j &gt;= <span class="number">0</span> &amp;&amp; data[j] &gt; data[j + <span class="number">1</span>]; j--) &#123;</span><br><span class="line">			temp = data[j + <span class="number">1</span>];</span><br><span class="line">			data[j + <span class="number">1</span>] = data[j];</span><br><span class="line">			data[j] = temp;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125; <span class="comment">// sortTwo end</span></span><br></pre></td></tr></table></figure>

<h3 id="复杂度分析"><a href="#复杂度分析" class="headerlink" title="复杂度分析"></a>复杂度分析</h3><table>
<thead>
<tr>
<th>平均时间复杂度</th>
<th>最好情况</th>
<th>最坏情况</th>
<th>空间复杂度</th>
</tr>
</thead>
<tbody><tr>
<td>O(n²)</td>
<td>O(n²)</td>
<td>O(n²)</td>
<td>O(1)</td>
</tr>
</tbody></table>
<p>插入排序所需的时间取决于输入元素的初始顺序。例如，对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比随机顺序的数组或是逆序数组进行排序要快得多。</p>
<h2 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h2><p>希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell 于1959 年提出而得名。</p>
<p>先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。</p>
<p>将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。<br>可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。</p>
<h3 id="算法描述-1"><a href="#算法描述-1" class="headerlink" title="算法描述"></a>算法描述</h3><p>1、选择一个增量序列 t1，t2，……，tk，其中 ti &gt; tj, tk = 1。</p>
<p>2、按增量序列个数 k，对序列进行 k 趟排序。</p>
<p>3、每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。</p>
<p>引用自网上一张图（侵删）：</p>
<p><img src="/2021/02/20/Java数据结构与算法/Java八大排序算法/image-20210220134535850.png" alt="image-20210220134535850"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] data)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> temp;</span><br><span class="line">	<span class="comment">// 增量每次都/2</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> step = data.length / <span class="number">2</span>; step &gt; <span class="number">0</span>; step /= <span class="number">2</span>) &#123;</span><br><span class="line">		<span class="comment">// 从增量那组开始进行插入排序，直至完毕</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = step; i &lt; data.length; i++) &#123;</span><br><span class="line">			temp = data[i];</span><br><span class="line">			<span class="keyword">int</span> j = i - step;</span><br><span class="line">			<span class="keyword">for</span> (; j &gt;= <span class="number">0</span> &amp;&amp; data[j] &gt; temp; j -= step) &#123;</span><br><span class="line">				<span class="comment">// 往后退一个step位置，让当前数据与之前前位进行比较</span></span><br><span class="line">				data[j + step] = data[j];</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="comment">// 退出内层循环，则说明找到了合适的位置，并将当前数据插入合适的位置中</span></span><br><span class="line">			data[j + step] = temp;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125; <span class="comment">// sort end</span></span><br></pre></td></tr></table></figure>

<h3 id="复杂度分析-1"><a href="#复杂度分析-1" class="headerlink" title="复杂度分析"></a>复杂度分析</h3><table>
<thead>
<tr>
<th>平均时间复杂度</th>
<th>最好情况</th>
<th>最坏情况</th>
<th>空间复杂度</th>
</tr>
</thead>
<tbody><tr>
<td>O(nlog2n)</td>
<td>O(nlog2n)</td>
<td>O(nlog2n)</td>
<td>O(1)</td>
</tr>
</tbody></table>
<p>希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。</p>
<h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><p>选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5 挪动到第二个5 后面）。</p>
<p>选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。</p>
<h3 id="算法描述："><a href="#算法描述：" class="headerlink" title="算法描述："></a>算法描述：</h3><p>1、从未排序序列中，找到关键字最小的元素。</p>
<p>2、如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换。</p>
<p>3、重复1、2步，直到排序结束。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] data)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 记录当前趟数的最小值的角标</span></span><br><span class="line">	<span class="keyword">int</span> minPos;</span><br><span class="line">	<span class="comment">// 交换的变量</span></span><br><span class="line">	<span class="keyword">int</span> temp;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; data.length; i++) &#123;</span><br><span class="line">		<span class="comment">// 新的趟数的起点</span></span><br><span class="line">		minPos = i;</span><br><span class="line">		<span class="comment">// 选出之后排序中值最小的位置</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; data.length; j++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (data[j] &lt; data[i]) &#123;</span><br><span class="line">				minPos = j;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 最小值不等于当前值时进行交换</span></span><br><span class="line">		<span class="keyword">if</span> (minPos != i) &#123;</span><br><span class="line">			temp = data[i];</span><br><span class="line">			data[i] = data[minPos];</span><br><span class="line">			data[minPos] = temp;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125; <span class="comment">// sort end</span></span><br></pre></td></tr></table></figure>

<h3 id="复杂度分析-2"><a href="#复杂度分析-2" class="headerlink" title="复杂度分析"></a>复杂度分析</h3><table>
<thead>
<tr>
<th>平均时间复杂度</th>
<th>最好情况</th>
<th>最坏情况</th>
<th>空间复杂度</th>
</tr>
</thead>
<tbody><tr>
<td>O(n²)</td>
<td>O(n²)</td>
<td>O(n²)</td>
<td>O(1)</td>
</tr>
</tbody></table>
<p>选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。</p>
<h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><h3 id="复杂度分析-3"><a href="#复杂度分析-3" class="headerlink" title="复杂度分析"></a>复杂度分析</h3><table>
<thead>
<tr>
<th>平均时间复杂度</th>
<th>最好情况</th>
<th>最坏情况</th>
<th>空间复杂度</th>
</tr>
</thead>
<tbody><tr>
<td>O(n²)</td>
<td>O(n²)</td>
<td>O(n²)</td>
<td>O(1)</td>
</tr>
</tbody></table>
<h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><p>冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。</p>
<h3 id="算法描述：-1"><a href="#算法描述：-1" class="headerlink" title="算法描述："></a>算法描述：</h3><p>描述一：</p>
<p>1、i从0开始，i与i+1比较，如果后面的数（i+1）小于前面的数（i），则交换。<br>2、i不断增加，直到i&lt;n-1（数组长度减一），一趟下来，可以让数组元素中的最大值排在数组的最后，直到完成。</p>
<p>描述二：</p>
<p>1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。</p>
<p>2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。</p>
<p>3、针对所有的元素重复以上的步骤，除了最后一个。</p>
<p>4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] data)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 测试用，记录执行了多少趟</span></span><br><span class="line">	<span class="keyword">int</span> num = <span class="number">0</span>;</span><br><span class="line">	<span class="comment">// 装载临时变量</span></span><br><span class="line">	<span class="keyword">int</span> temp;</span><br><span class="line">	<span class="comment">// 外层是排序的趟数</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; data.length - <span class="number">1</span>; i++) &#123;</span><br><span class="line">		<span class="comment">// 内层循环是当前趟数需要比较的次数</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; data.length - i - <span class="number">1</span>; j++) &#123;</span><br><span class="line">			<span class="comment">// 前一位与后一位相比较，如果前一位比后一位要大，则交换</span></span><br><span class="line">			<span class="keyword">if</span> (data[j + <span class="number">1</span>] &lt; data[j]) &#123;</span><br><span class="line">				temp = data[j + <span class="number">1</span>];</span><br><span class="line">				data[j + <span class="number">1</span>] = data[j];</span><br><span class="line">				data[j] = temp;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		num++;</span><br><span class="line">	&#125;</span><br><span class="line">	System.out.println(<span class="string">"Sort run frequency is : "</span> + num);</span><br><span class="line">&#125; <span class="comment">// sort end</span></span><br></pre></td></tr></table></figure>

<h3 id="复杂度分析-4"><a href="#复杂度分析-4" class="headerlink" title="复杂度分析"></a>复杂度分析</h3><table>
<thead>
<tr>
<th>平均时间复杂度</th>
<th>最好情况</th>
<th>最坏情况</th>
<th>空间复杂度</th>
</tr>
</thead>
<tbody><tr>
<td>O(n²)</td>
<td>O(n)</td>
<td>O(n²)</td>
<td>O(1)</td>
</tr>
</tbody></table>
<p>冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).</p>
<h3 id="冒泡排序优化"><a href="#冒泡排序优化" class="headerlink" title="冒泡排序优化"></a>冒泡排序优化</h3><p>如果数据足够乱的情况下，例如反序，需要数据长度-1趟才能将数据完整排好序。</p>
<p>但是在部分有序情况下，例如在第3趟比较后就已经得到了排好序的数组，就没有必要执行后面的计算了。我们可以做如下优化：</p>
<ul>
<li>如果在某趟排序中没有发生交换位置，那么我们可以认为该数组已经排好顺序了。（我们每趟排序的目的就是为了将当前趟最大的数置换到对应的位置上，如果没有发生置换说明已经是排好序的了）。</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">betterSort</span><span class="params">(<span class="keyword">int</span>[] data)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 测试用，记录执行了多少趟</span></span><br><span class="line">	<span class="keyword">int</span> num = <span class="number">0</span>;</span><br><span class="line">	<span class="comment">// 装载临时变量</span></span><br><span class="line">	<span class="keyword">int</span> temp;</span><br><span class="line">	<span class="comment">// 记录是否发生了置换，0代表没有发生置换，1代表发生了置换</span></span><br><span class="line">	<span class="keyword">int</span> isChange;</span><br><span class="line">	<span class="comment">// 外层是排序的趟数</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; data.length - <span class="number">1</span>; i++) &#123;</span><br><span class="line">		<span class="comment">// 每比较一趟就重新初始化为0</span></span><br><span class="line">		isChange = <span class="number">0</span>;</span><br><span class="line">		<span class="comment">// 内层循环是当前趟数需要比较的次数</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; data.length - i - <span class="number">1</span>; j++) &#123;</span><br><span class="line">			<span class="comment">// 前一位与后一位相比较，如果前一位比后一位要大，则交换</span></span><br><span class="line">			<span class="keyword">if</span> (data[j + <span class="number">1</span>] &lt; data[j]) &#123;</span><br><span class="line">				temp = data[j + <span class="number">1</span>];</span><br><span class="line">				data[j + <span class="number">1</span>] = data[j];</span><br><span class="line">				data[j] = temp;</span><br><span class="line"></span><br><span class="line">				<span class="comment">// 如果进到这里面了，说明发生了置换</span></span><br><span class="line">				isChange = <span class="number">1</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了</span></span><br><span class="line">		<span class="keyword">if</span> (isChange == <span class="number">0</span>) &#123;</span><br><span class="line">			<span class="keyword">break</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		num++;</span><br><span class="line">	&#125;</span><br><span class="line">	System.out.println(<span class="string">"betterSort run frequency is : "</span> + num);</span><br><span class="line">&#125; <span class="comment">// better sort end</span></span><br></pre></td></tr></table></figure>

<h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><p>快速排序由C. A. R. Hoare 在1962 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。</p>
<p>一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引&gt;从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。</p>
<h3 id="算法思想："><a href="#算法思想：" class="headerlink" title="算法思想："></a>算法思想：</h3><p>快速排序的基本思想：<strong>挖坑填数+分治法</strong>。</p>
<p>快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。</p>
<p>快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。</p>
<p>快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。</p>
<p>快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists），算法步骤：</p>
<p>1、从数列中挑出一个元素，称为”基准”（pivot）。</p>
<p>2、重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。</p>
<p>3、递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。</p>
<p>递归到最底部时，数列的大小是零或一，也就是已经排序好了。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] data, <span class="keyword">int</span> L, <span class="keyword">int</span> R)</span> </span>&#123;</span><br><span class="line">	System.out.println(<span class="string">"sort start, L : "</span> + L + <span class="string">" ,R : "</span> + R);</span><br><span class="line">	<span class="keyword">int</span> i = L;</span><br><span class="line">	<span class="keyword">int</span> j = R;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 交换的变量</span></span><br><span class="line">	<span class="keyword">int</span> temp;</span><br><span class="line">	<span class="comment">// 支点</span></span><br><span class="line">	<span class="keyword">int</span> pivot = data[L + (R - L) / <span class="number">2</span>];</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 左右两端进行扫描，只要两端没有交替，就一直扫描</span></span><br><span class="line">	<span class="keyword">while</span> (i &lt;= j) &#123;</span><br><span class="line">		<span class="comment">// 左边寻找直到比支点大的数</span></span><br><span class="line">		<span class="keyword">while</span> (pivot &gt; data[i]) &#123;</span><br><span class="line">			i++;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 右边寻找直到比支点小的数</span></span><br><span class="line">		<span class="keyword">while</span> (pivot &lt; data[j]) &#123;</span><br><span class="line">			j--;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 此时已经分别找到了比支点小的数（右边）、比支点大的数（左边），它们进行交换</span></span><br><span class="line">		<span class="keyword">if</span> (i &lt;= j) &#123;</span><br><span class="line">			temp = data[i];</span><br><span class="line">			data[i] = data[j];</span><br><span class="line">			data[j] = temp;</span><br><span class="line">			<span class="comment">// 左边右移一位</span></span><br><span class="line">			i++;</span><br><span class="line">			<span class="comment">// 右边左移一位</span></span><br><span class="line">			j--;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。</span></span><br><span class="line"></span><br><span class="line">	<span class="comment">// 左边再做排序，直到左边剩下一个数（递归出口）</span></span><br><span class="line">	<span class="keyword">if</span> (L &lt; j) &#123;</span><br><span class="line">		System.out.println(<span class="string">"sort left before, L : "</span> + L + <span class="string">" ,j : "</span> + j);</span><br><span class="line">		sort(data, L, j);</span><br><span class="line">		System.out.println(<span class="string">"sort left end, L : "</span> + L + <span class="string">" ,j : "</span> + j);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 右边再做排序，直到右边剩下一个数（递归出口）</span></span><br><span class="line">	<span class="keyword">if</span> (i &lt; R) &#123;</span><br><span class="line">		System.out.println(<span class="string">"sort right before, i : "</span> + i + <span class="string">" ,R : "</span> + R);</span><br><span class="line">		sort(data, i, R);</span><br><span class="line">		System.out.println(<span class="string">"sort right end, i : "</span> + i + <span class="string">" ,R : "</span> + R);</span><br><span class="line">	&#125;</span><br><span class="line">&#125; <span class="comment">// sort end</span></span><br></pre></td></tr></table></figure>

<h3 id="复杂度分析-5"><a href="#复杂度分析-5" class="headerlink" title="复杂度分析"></a>复杂度分析</h3><table>
<thead>
<tr>
<th>平均时间复杂度</th>
<th>最好情况</th>
<th>最坏情况</th>
<th>空间复杂度</th>
</tr>
</thead>
<tbody><tr>
<td>O(nlog₂n)</td>
<td>O(nlog₂n)</td>
<td>O(n²)</td>
<td>O(1)</td>
</tr>
</tbody></table>
<h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><p>归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用<strong>分治法（Divide and Conquer）</strong>的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。</p>
<p>归并排序可通过两种方式实现:</p>
<ul>
<li>自上而下的递归</li>
<li>自下而上的迭代</li>
</ul>
<p>递归法（假设序列共有n个元素）：</p>
<p>1、将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；</p>
<p>2、将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；</p>
<p>3、重复步骤2，直到所有元素排序完毕。</p>
<h3 id="算法思想"><a href="#算法思想" class="headerlink" title="算法思想"></a>算法思想</h3><p>迭代法归并操作的工作原理如下：</p>
<p>1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。</p>
<p>2、设定两个指针，最初位置分别为两个已经排序序列的起始位置。</p>
<p>3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。</p>
<p>4、重复步骤3 直到某一指针超出序列尾。</p>
<p>5、将另一序列剩下的所有元素直接复制到合并序列尾。</p>
<p>归并排序其实要做两件事：</p>
<ul>
<li>分解：将序列每次折半拆分</li>
<li>合并：将划分后的序列段两两排序合并</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] data, <span class="keyword">int</span> L, <span class="keyword">int</span> R)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 如果只有一个元素，那就不用排序了</span></span><br><span class="line">	<span class="keyword">if</span> (L == R) &#123;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">		<span class="comment">// 取中间的数，进行拆分</span></span><br><span class="line">		<span class="keyword">int</span> M = L + (R - L) / <span class="number">2</span>;</span><br><span class="line"></span><br><span class="line">		System.out.println(<span class="string">"sort left before, L : "</span> + L + <span class="string">" ,M : "</span> + M);</span><br><span class="line">		<span class="comment">// 左边的数不断进行拆分</span></span><br><span class="line">		sort(data, L, M);</span><br><span class="line">		System.out.println(<span class="string">"sort left end, L : "</span> + L + <span class="string">" ,M : "</span> + M);</span><br><span class="line"></span><br><span class="line">		System.out.println(<span class="string">"sort right before, M+1 : "</span> + (M + <span class="number">1</span>) + <span class="string">" ,R : "</span> + R);</span><br><span class="line">		<span class="comment">// 右边的数不断进行拆分</span></span><br><span class="line">		sort(data, M + <span class="number">1</span>, R);</span><br><span class="line">		System.out.println(<span class="string">"sort right end, M+1 : "</span> + (M + <span class="number">1</span>) + <span class="string">" ,R : "</span> + R);</span><br><span class="line"></span><br><span class="line">		System.out.println(<span class="string">"merge before, L: "</span> + L + <span class="string">", M+1 : "</span> + (M + <span class="number">1</span>) + <span class="string">" ,R : "</span> + R);</span><br><span class="line">		<span class="comment">// 合并</span></span><br><span class="line">		merge(data, L, M + <span class="number">1</span>, R);</span><br><span class="line">		System.out.println(<span class="string">"merge end, L: "</span> + L + <span class="string">", M+1 : "</span> + (M + <span class="number">1</span>) + <span class="string">" ,R : "</span> + R);</span><br><span class="line">	&#125;</span><br><span class="line">&#125; <span class="comment">// sort end</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span>[] data, <span class="keyword">int</span> L, <span class="keyword">int</span> M, <span class="keyword">int</span> R)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 左边数组的大小</span></span><br><span class="line">	<span class="keyword">int</span>[] leftData = <span class="keyword">new</span> <span class="keyword">int</span>[M - L];</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 右边数组的大小</span></span><br><span class="line">	<span class="keyword">int</span>[] rightData = <span class="keyword">new</span> <span class="keyword">int</span>[R - M + <span class="number">1</span>];</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 往这两个数组填充数据</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = L; i &lt; M; i++) &#123;</span><br><span class="line">		leftData[i - L] = data[i];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = M; i &lt;= R; i++) &#123;</span><br><span class="line">		rightData[i - M] = data[i];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> i = <span class="number">0</span>, j = <span class="number">0</span>;</span><br><span class="line">	<span class="comment">// data数组的第一个元素</span></span><br><span class="line">	<span class="keyword">int</span> k = L;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 比较两个数组的值，哪个小，就往数组上放</span></span><br><span class="line">	<span class="keyword">while</span> (i &lt; leftData.length &amp;&amp; j &lt; rightData.length) &#123;</span><br><span class="line">		<span class="comment">// 谁比较小，谁将元素放入大数组中，移动指针，继续比较下一个</span></span><br><span class="line">		<span class="keyword">if</span> (leftData[i] &lt; rightData[j]) &#123;</span><br><span class="line">			data[k] = leftData[i];</span><br><span class="line"></span><br><span class="line">			i++;</span><br><span class="line">			k++;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			data[k] = rightData[j];</span><br><span class="line"></span><br><span class="line">			j++;</span><br><span class="line">			k++;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 如果左边数组没有比较完，右边数组已经完了，那么将左边数组复制到大数组中（剩下的都是大数字）</span></span><br><span class="line">	<span class="keyword">while</span> (i &lt; leftData.length) &#123;</span><br><span class="line">		data[k] = leftData[i];</span><br><span class="line"></span><br><span class="line">		i++;</span><br><span class="line">		k++;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 如果右边数组没有比较完，左边数组已经完了，那么将右边数组复制到大数组中（剩下的都是大数字）</span></span><br><span class="line">	<span class="keyword">while</span> (j &lt; rightData.length) &#123;</span><br><span class="line">		data[k] = rightData[j];</span><br><span class="line"></span><br><span class="line">		j++;</span><br><span class="line">		k++;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125; <span class="comment">// merge end</span></span><br></pre></td></tr></table></figure>

<h3 id="复杂度分析-6"><a href="#复杂度分析-6" class="headerlink" title="复杂度分析"></a>复杂度分析</h3><table>
<thead>
<tr>
<th>平均时间复杂度</th>
<th>最好情况</th>
<th>最坏情况</th>
<th>空间复杂度</th>
</tr>
</thead>
<tbody><tr>
<td>O(nlog₂n)</td>
<td>O(nlog₂n)</td>
<td>O(nlog₂n)</td>
<td>O(1)</td>
</tr>
</tbody></table>
<p>从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn，, 又每步都是一个普通的合并子数组的过程， 时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。</p>
<p>归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比，它的主要缺点则是他所需的额外空间和N成正比。</p>
<h2 id="基数排序（桶排序）"><a href="#基数排序（桶排序）" class="headerlink" title="基数排序（桶排序）"></a>基数排序（桶排序）</h2><p>基数排序(radix sort)属于”分配式排序”(distribution sort)，又称”桶子法”(bucket sort)或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些”桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r 为所采取的基数，而m 为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。基数排序不同与其他的7种排序，其他7 种排序本质上都是按照交换或者比较来进行排序，但是基数排序并不是，它是按照分配，回收(分配到不同的位置上，然后回收)..不断分配..回收来进行排序，直到有序。</p>
<p>基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。</p>
<h3 id="算法思想-1"><a href="#算法思想-1" class="headerlink" title="算法思想"></a>算法思想</h3><p>基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。</p>
<p><strong>分配</strong>：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中</p>
<p><strong>收集</strong>：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[]。对新形成的序列L[]重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束</p>
<p>它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。</p>
<p>基数排序按照优先从高位或低位来排序有两种实现方案：</p>
<ul>
<li><p>MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列。MSD方式适用于位数多的序列。</p>
</li>
<li><p>LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。</p>
</li>
</ul>
<p>以LSD为例，从最低位开始，算法步骤：</p>
<p>1、取得数组中的最大数，并取得位数；</p>
<p>2、arr为原始数组，从最低位开始取每个位组成radix数组；</p>
<p>3、对radix进行计数排序（利用计数排序适用于小范围数的特点）；</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] data)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (data.length &lt;= <span class="number">1</span>) &#123;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 取得数组中最大的数，并取得位数</span></span><br><span class="line">	<span class="keyword">int</span> max = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; data.length; i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (max &lt; data[i]) &#123;</span><br><span class="line">			max = data[i];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 位数计算</span></span><br><span class="line">	<span class="keyword">int</span> maxDigit = <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span> (max / <span class="number">10</span> &gt; <span class="number">0</span>) &#123;</span><br><span class="line">		maxDigit++;</span><br><span class="line">		max = max / <span class="number">10</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 申请一个桶空间，二维数组</span></span><br><span class="line">	<span class="keyword">int</span>[][] buckets = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10</span>][data.length];</span><br><span class="line">	<span class="keyword">int</span> base = <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 从低位到高位，对每一位遍历，将所有元素分配到桶中</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; maxDigit; i++) &#123;</span><br><span class="line">		<span class="comment">// 存储各个桶中存储元素的数量</span></span><br><span class="line">		<span class="keyword">int</span>[] bktLen = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10</span>];</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 分配，将所有元素分配到桶中</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; data.length; j++) &#123;</span><br><span class="line">			<span class="keyword">int</span> whichBucket = (data[j] % base) / (base / <span class="number">10</span>);</span><br><span class="line">			buckets[whichBucket][bktLen[whichBucket]] = data[j];</span><br><span class="line">			bktLen[whichBucket]++;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 收集，将不同桶里的数据挨个捞出来，为下一轮高位排序做准备，由于靠近桶底的元素排名靠前，因此从桶底先捞</span></span><br><span class="line">		<span class="keyword">int</span> k = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> b = <span class="number">0</span>; b &lt; buckets.length; b++) &#123;</span><br><span class="line">			<span class="keyword">for</span> (<span class="keyword">int</span> p = <span class="number">0</span>; p &lt; bktLen[b]; p++) &#123;</span><br><span class="line">				data[k++] = buckets[b][p];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		base *= <span class="number">10</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125; <span class="comment">// sort end</span></span><br></pre></td></tr></table></figure>

<h3 id="复杂度分析-7"><a href="#复杂度分析-7" class="headerlink" title="复杂度分析"></a>复杂度分析</h3><table>
<thead>
<tr>
<th>平均时间复杂度</th>
<th>最好情况</th>
<th>最坏情况</th>
<th>空间复杂度</th>
</tr>
</thead>
<tbody><tr>
<td>O(d*(n + r))</td>
<td>O(d*(n + r))</td>
<td>O(d*(n + r))</td>
<td>O(n+r)</td>
</tr>
</tbody></table>
<p>其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r))。</p>
<p>备注：</p>
<p>基数排序更适合用于对时间, 字符串等这些 整体权值未知的数据 进行排序。</p>
<p>基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。</p>
<p>基数排序 vs 计数排序 vs 桶排序</p>
<p>这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：</p>
<p>1、基数排序：根据键值的每位数字来分配桶</p>
<p>2、计数排序：每个桶只存储单一键值</p>
<p>3、桶排序：每个桶存储一定范围的数值</p>
<h2 id="八大排序算法总结"><a href="#八大排序算法总结" class="headerlink" title="八大排序算法总结"></a>八大排序算法总结</h2><p>从时间复杂度来说：</p>
<p>1、平方阶O(n²)排序：<strong>各类简单排序：直接插入、直接选择和冒泡排序</strong></p>
<p>2、线性对数阶O(nlog₂n)排序：<strong>快速排序、堆排序和归并排序</strong></p>
<p>3、O(n1+§))排序，§是介于0和1之间的常数：<strong>希尔排序</strong></p>
<p>4、线性阶O(n)排序：<strong>基数排序，此外还有桶、箱排序</strong></p>

      
    </div>

    

    
    
    
    <div>
      
        <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束<i class="fa fa-paw"></i>感谢您的阅读-------------</div>
    
</div>
      
    </div>

    

    
      
    
    

    

    <footer class="post-footer">
      
        
          
        
        <div class="post-tags">
          
            <a href="/tags/排序算法/" rel="tag"># 排序算法</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2021/02/19/Java数据结构与算法/Java数据结构与算法概览/" rel="next" title="Java数据结构与算法概览">
                <i class="fa fa-chevron-left"></i> Java数据结构与算法概览
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2021/02/22/Linux相关/Linux之vim使用详解/" rel="prev" title="Linux之vim使用详解">
                Linux之vim使用详解 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>


  </div>


          </div>
          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            Table of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            Overview
          </li>
        </ul>
      

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/geass.jpg" alt="MingRongChen">
            
              <p class="site-author-name" itemprop="name">MingRongChen</p>
              <div class="site-description motion-element" itemprop="description">O Captain! My Captain!</div>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/archives/">
                
                    <span class="site-state-item-count">23</span>
                    <span class="site-state-item-name">posts</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  
                    
                      <a href="/categories/">
                    
                  
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">9</span>
                    <span class="site-state-item-name">categories</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  
                    
                      <a href="/tags/">
                    
                  
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">21</span>
                    <span class="site-state-item-name">tags</span>
                  </a>
                </div>
              
            </nav>
          

          

          

          
            <div class="links-of-author motion-element">
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="https://github.com/mingrongchen" title="GitHub &rarr; https://github.com/mingrongchen" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="mailto:825296313@qq.com" title="E-Mail &rarr; mailto:825296313@qq.com" rel="noopener" target="_blank"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                </span>
              
            </div>
          

          

          
          

          
            
          
          

        </div>
      </div>

      
      <!--noindex-->
        <div class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
            
            
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#Java八大排序算法"><span class="nav-number">1.</span> <span class="nav-text">Java八大排序算法</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#概要"><span class="nav-number">1.1.</span> <span class="nav-text">概要</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#直接插入排序算法"><span class="nav-number">1.2.</span> <span class="nav-text">直接插入排序算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法描述"><span class="nav-number">1.2.1.</span> <span class="nav-text">算法描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度分析"><span class="nav-number">1.2.2.</span> <span class="nav-text">复杂度分析</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#希尔排序"><span class="nav-number">1.3.</span> <span class="nav-text">希尔排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法描述-1"><span class="nav-number">1.3.1.</span> <span class="nav-text">算法描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度分析-1"><span class="nav-number">1.3.2.</span> <span class="nav-text">复杂度分析</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#选择排序"><span class="nav-number">1.4.</span> <span class="nav-text">选择排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法描述："><span class="nav-number">1.4.1.</span> <span class="nav-text">算法描述：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度分析-2"><span class="nav-number">1.4.2.</span> <span class="nav-text">复杂度分析</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#堆排序"><span class="nav-number">1.5.</span> <span class="nav-text">堆排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度分析-3"><span class="nav-number">1.5.1.</span> <span class="nav-text">复杂度分析</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#冒泡排序"><span class="nav-number">1.6.</span> <span class="nav-text">冒泡排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法描述：-1"><span class="nav-number">1.6.1.</span> <span class="nav-text">算法描述：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度分析-4"><span class="nav-number">1.6.2.</span> <span class="nav-text">复杂度分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#冒泡排序优化"><span class="nav-number">1.6.3.</span> <span class="nav-text">冒泡排序优化</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#快速排序"><span class="nav-number">1.7.</span> <span class="nav-text">快速排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法思想："><span class="nav-number">1.7.1.</span> <span class="nav-text">算法思想：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度分析-5"><span class="nav-number">1.7.2.</span> <span class="nav-text">复杂度分析</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#归并排序"><span class="nav-number">1.8.</span> <span class="nav-text">归并排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法思想"><span class="nav-number">1.8.1.</span> <span class="nav-text">算法思想</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度分析-6"><span class="nav-number">1.8.2.</span> <span class="nav-text">复杂度分析</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#基数排序（桶排序）"><span class="nav-number">1.9.</span> <span class="nav-text">基数排序（桶排序）</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法思想-1"><span class="nav-number">1.9.1.</span> <span class="nav-text">算法思想</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度分析-7"><span class="nav-number">1.9.2.</span> <span class="nav-text">复杂度分析</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#八大排序算法总结"><span class="nav-number">1.10.</span> <span class="nav-text">八大排序算法总结</span></a></li></ol></li></ol></div>
            

          </div>
        </div>
      <!--/noindex-->
      

      

    </div>
  </aside>
  


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2019 – <span itemprop="copyrightYear">2022</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">MingRong</span>

  

  
</div>









        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="post-meta-item-icon">
      <i class="fa fa-user"></i>
    </span>
    <span class="site-uv" title="Total Visitors">
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
    </span>
  

  
    <span class="post-meta-divider">|</span>
  

  
    <span class="post-meta-item-icon">
      <i class="fa fa-eye"></i>
    </span>
    <span class="site-pv" title="Total Views">
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
    </span>
  
</div>









        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

    

    
  </div>

  

<script>
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>


























  
  <script src="/lib/jquery/index.js?v=3.4.1"></script>

  
  <script src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>


  


  <script src="/js/utils.js?v=7.2.0"></script>

  <script src="/js/motion.js?v=7.2.0"></script>



  
  


  <script src="/js/affix.js?v=7.2.0"></script>

  <script src="/js/schemes/pisces.js?v=7.2.0"></script>



  
  <script src="/js/scrollspy.js?v=7.2.0"></script>
<script src="/js/post-details.js?v=7.2.0"></script>



  


  <script src="/js/next-boot.js?v=7.2.0"></script>


  

  

  

  


  


  




  

  

  

  

  

  

  

  

  

  

  

  

  

  

<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"log":false,"model":{"scale":1.5,"hHeadPos":0.5,"vHeadPos":0.618,"jsonPath":"/live2dw/assets/z16.model.json"},"display":{"superSample":2,"position":"left","width":150,"height":300,"hOffset":0,"vOffset":-20},"mobile":{"show":false,"scale":0.5,"hOffset":0,"vOffset":-10},"react":{"opacity":0.8,"opacityDefault":0.7,"opacityOnHover":0.2}});</script></body>
</html>
